package name.huzhenbo.java.algorithm.talent;

import java.util.ArrayList;
import java.util.List;

/**
 * Select a good person from a list of people. Good person only tell truth, but bad person is not sure.
 * In the list, more than half people are good.
 */
class GoodPersonFinder {
    private Person[] people;

    public GoodPersonFinder(Person[] people) {
        this.people = people;
    }

    /**
     * O(n2)
     *
     * If the person is told by more than half people that he is good person, than he must be good person.
     * Because if he is bad person, then must be more than half people tell he is bad.
     *
     */
    public Person go() {
        for (Person current : people) {
            int count = 0;
            for (Person another: people) {
                if (current == another) continue;
                if (another.tell(current)) {
                    count++;
                }
            }
            if (count >= people.length / 2) {
                return current;
            }
        }

        return null;
    }

    /**
     * The idea is to remove bad person:
     * 1. when both tell each other is good person, then they may both good people or both tell lies.
     * 2. otherwise, at least one of them are bad person, then delete both of them.
     * In the left people, good person are still more than half. Continue 1 and 2.
     *
     * Tail recursive, best is O(n)
     *
     * Not finish yet. has 1 TODO
     */
    public Person goFaster() {
        List<Integer> potentials = new ArrayList<Integer>();
        for (int i = 0; i < people.length; i++) {
            potentials.add(i);
        }
        return _goFaster(potentials);
    }

    private Person _goFaster(List<Integer> left) {
        List<Integer> potentials = new ArrayList<Integer>();
        int half = left.size() / 2;
        for (int i = 0; i < half; i++) {
            int index1 = left.get(i);
            int index2 = left.get(i + half);
            // TODO: deal with the condition: when 1 and 2 are both bad people, and they both tell lies.
            if (bothGood(index1, index2)) {
                potentials.add(index1);
                potentials.add(index2);
            }
        }

        // when the number of person is odd, add the last one back.
        if(half * 2 < left.size()) potentials.add(left.get(left.size() - 1));
        // when only one left, then he must be good person.
        // or when no more bad person deleted, then all the left are good person.
        if(potentials.size() == left.size()){
            return people[potentials.get(0)];
        }
        return _goFaster(potentials);
    }

    private boolean bothGood(int index1, int index2) {
        return people[index1].tell(people[index2])
                && people[index2].tell(people[index1]);
    }

}
